\documentclass{beamer}
\usepackage{nicefrac}
\usepackage[latin1]{inputenc}
\usepackage{custom-cmds}
\usepackage{subfigure}      % Wrap figures in text
\usetheme{Warsaw}
\title[Linear communication complexity in SMC]{Master's Thesis: Linear
  communication complexity in Secure Multiparty Computation}
\author{Kasper Damgaard}
\institute{Aarhus University}
\date{\today}
\begin{document}

\begin{frame}
\titlepage
\end{frame}

\part{Contents}
\section{contents}
\begin{frame}{contents}
  
\begin{itemize}
  \item Introduction to SMC
  \item Basic tools
  \item Player elimination framework
  \item Evaluation
  \item Conclusion
\end{itemize}
\end{frame}

\section{Introduction}
\subsection{intro}
\begin{frame}{Introduction}
  \textit{Secure Multiparty Computation (SMC):}\newline \ \newline
  SMC is the problem of getting $n$ parties to compute a function $f$
  given some input $x$. This is done in a way such that no central
  component is needed. We assume up to $t\leq \nicefrac{n}{3}$
  corrupted parties.
\end{frame}

\begin{frame}
  In our case we require that the protocol is perfectly secure, which
  means that it satisfies the following two requirements:
  \begin{itemize}
    \pause \item \textit{Perfect correctness:} With probability 1, all parties
    receive correct outputs based on the inputs.  
    \pause \item \textit{Perfect privacy:} The adversary cannot learn any more 
    information than the input and output of the corrupted parties, 
    even if given unlimited time and computing power.
  \end{itemize}
\end{frame}

\begin{frame}
  \textit{We want to:}\newline
  implement a program that can do perfectly secure
  multiparty-computation in linear communication complexity. %% Explain here what this means
\end{frame}

\subsection{Basic tools}
\begin{frame}{Basic tools}
  We need some basic (and not so basic) tools:
  \begin{itemize}
    \pause \item Secret sharing
    \pause \item Broadcasting
    \pause \item The Berlekamp-Welch algorithm
    \pause \item Hyper-invertible matrices
  \end{itemize}
\end{frame}

% \begin{frame}{Secret sharing}
%   The form of secret sharing used is Shamirs Secret Sharing
%   Scheme. Works by choosing random coefficients for a polynomial $f$
%   of degree $t$ and dealing the share $f(i)$ to player $P_i$.
% \end{frame}

% \begin{frame}{Broadcasting}
%   Not implemented as there was simply not enough time. \newline
%   Instead: We assume that a party sends the same to all other parties
%   when he was supposed to broadcast.
% \end{frame}

% \begin{frame}{Berlekamp-Welch}
%   Algorithm for weeding out unwanted errors created by the corrupted
%   players. 
% \end{frame}

% \begin{frame}{Hyper-invertible Matrix}
%   This new invention enables us to compute $O(n)$ perfectly random
%   sharings using just $O(n^2)$ time and space. 
% \end{frame}

\section{Player elimination}
\begin{frame}{Player Elimination Framework}
  Player elimination is used to transform a detectable protocol into a
  robust protocol by eliminating pairs of players where at least one
  of them are corrupt.
\end{frame}

\section{Evaluation}
\subsection{Overhead}
\begin{frame}{Evaluating overhead}
  \figtwo{bytes_small.jpg}{bytes_small}{Total bytes send for small
    circuit}{speed_small.jpg}{speed_small}{Speed of the program for
    small circuit}{}
\end{frame}

\subsection{linear communication complexity}
\begin{frame}{Evaluating linear communication complexity - prep phase}
  \figtwo{pbytes_cm_25.jpg}{pbytes_cm_25}{bytes send during preparation
  phase}{pspeed_cm_25.jpg}{pspeed_cm_25}{time spend during preparation
  phase}{\caption{With $25$ multiplication gates}}
\end{frame}

\begin{frame}{Evaluating linear communication complexity - comp phase}
  \figtwo{cbytes_cm_25.jpg}{cbytes_cm_25}{bytes send during computation
  phase}{cspeed_cm_25.jpg}{cspeed_cm_25}{time spend during computation
  phase}{\caption{With $25$ multiplication gates}}
\end{frame}

\begin{frame}{Evaluating linear communication complexity - combined}
  \figtwo{tbytes_cm_25.jpg}{tbytes_cm_25}{bytes send in the combined
  phases}{tspeed_cm_25.jpg}{tspeed_cm_25}{time spend in the combined
  phases}{\caption{With $25$ multiplication gates}}
\end{frame}

\subsection{linearity in $c_M$}
\begin{frame}{Showing linearity in $c_M$}
  \figtwo{bytes_mult_vary_5.jpg}{bytes_mult_vary_5}{Total bytes send
    for circuit with varying $c_M$}{speed_mult_vary_5.jpg}
  {speed_mult_vary_5}{Speed of the program for circuit with varying 
    $c_M$}{\caption{Varying $c_M$ with $n=5$}}
\end{frame}

\section{Conclusion}
\begin{frame}
  I have:
  \begin{itemize}
    \item implemented the theoretical paper and evaluated it.
    \item Validated results for small circuits and small $n$. 
    \item Rendered it probable that the theory holds for larger $n$
      and circuits. 
  \end{itemize}
\end{frame}

\end{document}